package sort;

/**
 * @Author wangtengyu
 * @Create 2018-09-10-10:20
 *
 *
 * 要点 1.定义一个基准元素，一般选取最左边或者最右边的 2.定义左指针和右指针，两个指针不停的移动 停下来有两种情况 1.左指针等于右指针了，此时，将指针所指向的值与基准元素互换，然后对基准元素两边的元素继续进行快速排序，最后就是一个完整的排序,通过递归
 * 2.左指针遇到大于基准元素的值，停下。右指针遇到小于基准元素的值，停下。两者互换，保证基准元素右边的值大于基准元素，基准元素左边的值小于基准元素
 */
public class QuickSort {

  public void sort(int[] array) {
    quickSort(array, 0, array.length - 1);
  }


  public void quickSort(int[] array, int left, int right) {
    //left大于right，排序完成
    if (left >= right) {
      return;
    }

    //对分割后的两侧的数组进行排序
    int partition = partition(array, left, right);
    quickSort(array, left, partition - 1);
    quickSort(array, partition + 1, right);
  }

  private int partition(int[] array, int left, int right) {

    int i = left;
    int j = right + 1;

    int key = array[left];

    while (true) {
      while (i < right && array[++i] < key) {
        //i<right  ++i最大就是right 不越界
        //用++i而不是i++ 是因为下面还用用到当前的i，不能搞乱了。
      }
      while (j > left && array[--j] > key) {
        //j>left --j最小就是left 保证不越界
      }
      if (i >= j) {
        break;
      } else {
        swap(array, i, j);
      }
    }
    swap(array, left, j);
    return j;
  }

  private void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  public void printArray(int[] array) {
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
  }


  public static void main(String[] args) {
    int[] array = new int[]{32, 12, 23, 45, 12, 134, 5, 1, 6};
    QuickSort quickSort = new QuickSort();
    quickSort.sort(array);
    quickSort.printArray(array);
  }
}
